<?php
/*
剑指 Offer 25. 合并两个排序的链表
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
限制：

0 <= 链表长度 <= 1000



难度：简单

https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/


*/

require_once '../class/ListNode.class.php';
$arr1 = [1,2,4,];
$arr2 = [1,3,4,];
$head1 = array2LinkList($arr1);
$head2 = array2LinkList($arr2);
$obj = new Code_Offer25();
$res = $obj->main($head1, $head2);
fetchNode($res);

class Code_Offer25
{
    public function main($head1, $head2)
    {
        $head = new ListNode();
        $cur = $head;
        while ($head1 || $head2) {
            if ($head1 != null && $head2 == null) {
                $cur->next = $head1;
                $head1 = $head1->next;
            } else if ($head1 == null && $head2 != null) {
                $cur->next = $head2;
                $head2 = $head2->next;
            } else if ($head1->val < $head2->val) {
                $cur->next = $head1;
                $head1 = $head1->next;
            } else {
                $cur->next = $head2;
                $head2 = $head2->next;
            }
            $cur = $cur->next;
        }
        return $head->next;
    }
}